package 动态规划;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class NC91最长递增子序列 {

    /**
     * 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
     * 输入
     * [2,1,5,3,6,4,8,9,7]
     * 返回值
     * [1,3,4,8,9]
     */

    //dp依靠end,不依靠原dp,造使后面的dp可能会小,非求长度的模式
    public int[] LIS (int[] arr) {

        System.out.println("arr:"+JSON.toJSONString(arr));
        /**
         * 利用两个数组,一个是end,一个是dp
         * end代表当前最优dp的最小结尾值num
         * dp就是dp
         */
        int[] dp=new int[arr.length];
        int[] end=new int[arr.length];
        dp[0]=1;
        end[0]=arr[0];
        int endIndex=0;

        for (int i = 1; i < arr.length; i++) {

            if(arr[i]>end[endIndex]){
                endIndex++;
                end[endIndex]=arr[i];
                dp[i]=endIndex+1;
            }else{
                /**
                 * 维护end数组,然end数组每一位都是最小的
                 * 维护过程中,可能会动到最后一个元素,那么就更好了
                 */
                //从end数组中找到第一位比arr[i]大于等于的元素
                int left=0;
                int right=endIndex;//当前end就size-1,最后一位
                int mid=0;
                while (left<=right){
                    mid=(right-left)/2+left;
                    if (end[mid]>arr[i]){
                        //左移动
                        right=mid-1;
                    }else{
                        //右移动
                        left=mid+1;
                    }
                }
                end[left]=arr[i];
                /**
                 * 使用end,就可以让dp不依赖于原dp,而依赖于end
                 */
                dp[i]=left+1;
            }
            //重点:一定不要每个都给它当前最长,只给符合的人!
//            dp[i]=endIndex+1;
        }

        System.out.println("dp :"+JSON.toJSONString(dp));
        System.out.println("end:"+JSON.toJSONString(end));
        endIndex++;//坐标转为size

        //最终依靠的是dp,第一个do
        int[] res = new int[endIndex];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (dp[i] == endIndex) {
                res[--endIndex] = arr[i];
            }
        }
        System.out.println(JSON.toJSONString(res));

        return res;
    }

    public static void main(String[] args) {
        NC91最长递增子序列 n=new NC91最长递增子序列();
        int[] result = n.LIS(new int[]{2, 1, 5, 3, 4, 6, 8, 9, 7});
        System.out.println(JSON.toJSONString(result));
    }

}
